package leetcode.day_2021_03_8_2021_03_14;

import java.util.*;

/**
 *
 */
public class LeetCode0047 {
    static List<List<Integer>> result = new ArrayList<>();
    static Set<String> set = new HashSet<>();

    public static List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        slove(nums, used, new ArrayList<>());
        return result;
    }

    public static void slove(int[] nums, boolean[] used, List<Integer> list) {
        if (list.size()==nums.length && !set.contains(list.toString())) {
            set.add(list.toString());
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i=0; i<nums.length; i++) {
            if (used[i]) continue;
            list.add(nums[i]);
            used[i] = true;
            slove(nums, used, list);
            used[i] = false;
            list.remove(list.size()-1);
        }
    }

    public static void main(String[] args) {
        System.out.println(permuteUnique(new int[]{1,2,3}));
    }
}
